package 我的Java学习_算法基础.day_07;

/**
 * @author 挚爱之夕
 * @date 2021/8/22 - 08 - 22 - 14:47
 * @Description: 我的Java学习.day_07
 * @Version: 1.0
 */
public class _120_困难的串 {
    public static void main(String[] args) {
        int n = 10;
        int l = 4;
        dfs(l,n,"");
    }
    static int count;
    private static void dfs(int l,int n,String prefix){
        //尝试在prefix后追加一个字符
        for(char i = 'A';i<'A'+l;i++){
            if(isHard(prefix,i)){ //是困难的串，就组合起来输出
                String x = prefix +i;
                System.out.println(x);
                count++;
                if(count==n){
                    System.exit(0);
                }
                dfs(l,n,x);
            }
        }
    }

    /**
     * prefix 是困难的串，判断加上i是否为困难的串
     * 1.遍历所有的长度为偶数的子串，看是否对称
     * 2.prefix 是困难的串 ABA  i  A!=i  AB!=Ai
     * @param prefix
     * @param i
     * @return
     */
    private static boolean isHard(String prefix, char i) {
        int count = 0;//截取的宽度
        for(int j = prefix.length()-1;j>=0;j-=2){
            final String s1 = prefix.substring(j,j+count+1);
            final String s2 = prefix.substring(j+count+1)+i;
            if(s1.equals(s2))
                return false;
            count++;
        }
        return true;
    }
}
